package cn.edu.xjtu.work.findShortestSubArray;

import java.util.HashMap;
import java.util.Map;

/**
 * 697. 数组的度
 * 
 * 给定一个非空且只包含非负数的整数数组 nums，数组的度的定义是指数组里任一元素出现频数的最大值。
 * 
 * 你的任务是在 nums 中找到与 nums 拥有相同大小的度的最短连续子数组，返回其长度。
 * 
 * 来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/degree-of-an-array
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Solution {
    public static void main(String[] args) {
        Solution solu = new Solution();
        int[] nums = { 1, 2, 2, 3, 1, 4, 2 };
        System.out.println(solu.findShortestSubArray(nums));
    }

    public int findShortestSubArray(int[] nums) {
        Map<Integer, node> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if (map.containsKey(nums[i])) {
                map.get(nums[i]).countPlus(i);
            } else {
                map.put(nums[i], new node(i));
            }
        }

        int maxDegree = 0;
        int minLen = nums.length;
        for (Map.Entry<Integer, node> n : map.entrySet()) {
            if (n.getValue().count == maxDegree) {
                minLen = Math.min(minLen, n.getValue().getLen());
            } else if (n.getValue().count > maxDegree) {
                maxDegree = n.getValue().count;
                minLen = n.getValue().getLen();
            }
        }
        return minLen;
    }
}

class node {
    int count = 1;
    int l;
    int r;

    public node(int l) {
        this.l = l;
        this.r = l;
    }

    public void countPlus(int i) {
        this.count++;
        r = i;
    }

    public int getLen() {
        return r - l + 1;
    }
}
